package 树与图.字典树;

/**
 * 二叉树的最近公共祖先
 * 题目分析： 这个问题可以这样理解，给定一个二叉树以及其中的两个节点，然后找到这两个节点的公共祖先
 * 最近公共祖先的定义为：对于树中的两个节点 p 和 q，最近公共祖先表示为一个节点 x，满足 x 是 p 或 q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。
 *
 * 解题思路： 使用递归解决
 * 1:递归的终止条件，当root为空或者root 等于p 或者 q时，返回root
 * 2：递归左右子树，递归查找左子树和右子树中是否存储p和q，如果都存在，则证明当前root就是最近公共祖先
 * 3：采用后续遍历： 此题要先从左右子树开始找起，所以使用左右根的后续遍历方式
 * 4： 判断条件：
 *    - 如果 p 和 q分别在当前根root中的左右子树中，那么root就是最近公共祖先
 *    - 如果 p和 q都存在于左子树中，那么返回左子树的查找结果
 *    - 如果 p 和 q都存在于右子树中，那么返回右子树的查找结果
 *    - 如果上述情况都不符合，那么就证明没有公共祖先，返回null
 * 根据解题思路翻译出代码
 *
 * @Author lf
 * @Date 3/26/2024
 */
public class LowestCommonAncestor236 {

    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        // 递归终止条件
        if(root == null || root == p || root == q){
            return root;
        }
        //后续遍历，左右根
        TreeNode left = lowestCommonAncestor(root.left, p, q);
        TreeNode right = lowestCommonAncestor(root.right, p, q);

        // 如果p和 q在左右子树中，那么left，right都不为空
        if(left !=null && right!=null){
            // 返回当前根节点
            return root;
        }else if(left == null){  // 左子树为空，返回右子树的查询结果
            return right;
        }else { // 右子树为空，返回左子树的查询结果
            return left;
        }
    }

        class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;
        TreeNode(int x) { val = x; }
    }
}
